package pro.softzhang.algo.lc1000;

import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 
 */
@XOptimal
public class LC1071_GreatestCommonDivisorOfStrings {
    public static void main(String[] args) {

    }

    @XOptimal
    static class Solution {
        public String gcdOfStrings(String str1, String str2) {
            if(!(str1 + str2).equals(str2 + str1)) {
                return "";
            }
            return str1.substring(0, gcd(str1.length(), str2.length()));
        }

        /**
         * 迭代GCD
         * @param dividend
         * @param divisor
         * @return
         */
        public int gcd(int dividend, int divisor) {
            int remainder = dividend % divisor;
            while (remainder != 0) {
                dividend = divisor;
                divisor = remainder;
                remainder = dividend % divisor;
            }
            return divisor;
        }

        /**
         * 递归GCD
         * @param dividend
         * @param divisor
         * @return
         */
        public int gcd1(int dividend, int divisor) {
            return divisor == 0 ? dividend : gcd(divisor, dividend % divisor);
        }
    }
}
